package 数据结构;

import common.TreeNode;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

/**
 * @author zhangmin
 * @create 2021-11-28 14:29
 * 树
 */
public class Tree02 {

    /**==============================================================================================================================================
     * JZ55 二叉树的深度
     * 输入一棵二叉树，求该树的深度。从根结点到叶结点依次经过的结点（含根、叶结点）形成树的一条路径，最长路径的长度为树的深度，根节点的深度视为 1 。
     * 递归
     * */
    public int TreeDepth(TreeNode root) {
        if(root==null) return 0;
        return 1+ Math.max(TreeDepth(root.left),TreeDepth(root.right));
    }
    /**==============================================================================================================================================
     * JZ77 按之字形顺序打印二叉树
     * 给定一个二叉树，返回该二叉树的之字形层序遍历，（第一层从左向右，下一层从右向左，一直这样交替）
     * 1、层序遍历，奇数行反转链表
     * */
    void reverse(ArrayList<Integer> list){
        int i=0,j=list.size()-1;
        while (i<j){
            int temp=list.get(i);
            list.set(i,list.get(j));
            list.set(j, temp);
            i++;j--;
        }
    }
    public ArrayList<ArrayList<Integer>> Print1(TreeNode pRoot) {
        if (pRoot==null)return new ArrayList<>();
        Queue<TreeNode> queue=new LinkedList<>();  //这里不要用优先队列，会有比较问题
        ArrayList<ArrayList<Integer>> res=new ArrayList<>();
        queue.offer(pRoot);
        while (!queue.isEmpty()){
            int levelNum=queue.size();
            ArrayList<Integer> level=new ArrayList<>();
            for (int i = 0; i < levelNum; i++) {
                TreeNode cur=queue.poll();
                level.add(cur.val);
                if (cur.left!=null){
                    queue.offer(cur.left);
                }
                if (cur.right!=null){
                    queue.offer(cur.right);
                }
            }
            res.add(level);
        }
        for (int i = 0; i < res.size(); i++) {
            if (i%2==1){
                reverse(res.get(i));
            }
        }
        return res;
    }

    /**==============================================================================================================================================
     * JZ54 二叉搜索树的第k个节点
     * 给定一棵结点数为n 二叉搜索树，请找出其中的第 k 小的TreeNode结点值。不能查找的情况，如二叉树为空，则返回-1，或者k大于n等等，也返回-1
     * 1、中序遍历（从小到大）找到第k个元素即可
     * 2.需要在二叉树节点中维护额外信息。每个节点需要记录，以自己为根的这棵二叉树有多少个节点。
     * */
    List<Integer> list=new ArrayList<>();
    void midOrderSearch(TreeNode root){
        if (root==null) return;
        midOrderSearch(root.left);
        list.add(root.val);
        midOrderSearch(root.right);
    }
    public int KthNode (TreeNode proot, int k) {
        if (proot==null||k==0) return -1;
        midOrderSearch(proot);
        if (list.size()<k) return -1;
        return list.get(k-1);
    }

    /**==============================================================================================================================================
     * JZ7 重建二叉树
     * 给定节点数为 n 二叉树的前序遍历和中序遍历结果，请重建出该二叉树并返回它的头结点。
     * 递归：前序遍历的首个元素即为跟节点可以在中序遍历中划分出左右子树，并且得到左右子树的个数。递归构造左右子树
     * */
    TreeNode reBuild(int[] pre,int[] vin,int p_start,int p_end,int v_start,int v_end){
        if (p_start<0||p_end>pre.length||p_start>p_end||v_start<0||v_end>vin.length||v_start>v_end)
            return null;
        int rootVal=pre[p_start];
        TreeNode root=new TreeNode(rootVal);
        //找到根节点在中序遍历中的下标
        int indexVin=v_start;
        for (int i = v_start; i <=v_end ; i++) {
            if (vin[i]==rootVal){
                indexVin=i;
                break;
            }
        }
        //得到左右子树的个数
        int leftNum=indexVin-v_start;
        int rightNum=v_end-indexVin;
        root.left=reBuild(pre,vin,p_start+1,p_start+leftNum,v_start,indexVin-1);
        root.right=reBuild(pre,vin,p_start+leftNum+1,p_end,indexVin+1,v_end);
        return root;
    }
    public TreeNode reConstructBinaryTree(int [] pre,int [] vin) {
        if (pre.length==0||pre.length!=vin.length) return null;
        return reBuild(pre,vin,0,pre.length-1,0,vin.length-1);
    }

    /**==============================================================================================================================================
     * JZ26 树的子结构
     * 输入两棵二叉树A，B，判断B是不是A的子结构。
     * 递归，递归函数用于判断root2为根的树是否是root1为根的树的子结构。遍历root1中的每个节点，判断它是否是保护root2子结构
     * */
    boolean isSubtree(TreeNode root1,TreeNode root2){
        //当节点 root2 为空：说明树 root2 已匹配完成（越过叶子节点），因此返回 true ；
        if (root2==null) return true;
        //当节点 A 为空：说明已经越过树 A 叶子节点，即匹配失败，返回 false；当节点 A和 B 的值不同：说明匹配失败，返回 false ；
        if (root1==null||root1.val!=root2.val) return false;
        return isSubtree(root1.left,root2.left)&&isSubtree(root1.right, root2.right);
    }

    public boolean HasSubtree(TreeNode root1,TreeNode root2) {
        //先序遍历A中的每个节点
        if (root2==null||root1==null) return false;
        return isSubtree(root1,root2)||HasSubtree(root1.left,root2)||HasSubtree(root1.right,root2);
    }

    /**==============================================================================================================================================
     * JZ27 二叉树的镜像
     * 操作给定的二叉树，将其变换为源二叉树的镜像。
     * 递归，自底向上交换每个节点的左右子树
     * */
    public TreeNode Mirror (TreeNode pRoot) {
        if (pRoot==null) return null;
        TreeNode right = Mirror(pRoot.right);
        TreeNode left = Mirror(pRoot.left);
        pRoot.left=right;
        pRoot.right=left;
        return pRoot;
    }

    /**==============================================================================================================================================
     * JZ32 从上往下打印二叉树
     * 不分行从上往下打印出二叉树的每个节点，同层节点从左至右打印。请你将打印的结果存放到一个数组里面，返回。
     * 层序遍历
     * */
    public ArrayList<Integer> PrintFromTopToBottom(TreeNode root) {
        ArrayList<Integer> res=new ArrayList<>();
        if (root==null) return res;
        Queue<TreeNode> queue=new LinkedList<>();
        queue.offer(root);
        while (!queue.isEmpty()){
            TreeNode cur=queue.poll();
            res.add(cur.val);
            if (cur.left!=null) queue.offer(cur.left);
            if (cur.right!=null) queue.offer(cur.right);
        }
        return res;
    }

    /**==============================================================================================================================================
     * JZ33 二叉搜索树的后序遍历序列
     * 输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历的结果。如果是则返回 true ,否则返回 false 。假设输入的数组的任意两个数字都互不相同。
     * 递归：后序遍历的最后一个节点即为根节点，需要有一个分界点，使得前半部分全都比根节点小，后半部分全都比根节点大。
     * 左子树中所有节点的值 < 根节点的值；右子树中所有节点的值 >根节点的值；其左、右子树也分别为二叉搜索树。
     * */
    boolean isBST(int[] sequence,int start,int end){
        if (start>=end) return true;
        int rootNum=sequence[end];
        //记录左右子树的分割点,[start,index)是左子树，[index,end)是右子树
        int p=start;
        while (sequence[p]<rootNum) p++;
        int index=p;
        while (sequence[p]>rootNum) p++;
        if (p!=end) return false;
        return isBST(sequence,start,index-1)&&isBST(sequence,index,end-1);
    }
    public boolean VerifySquenceOfBST(int [] sequence) {
        if (sequence.length==0) return false;
        return isBST(sequence,0,sequence.length-1);
    }

    /**==============================================================================================================================================
     * JZ82 二叉树中和为某一值的路径(一)
     * 给定一个二叉树root和一个值 sum ，判断是否有从根节点到叶子节点的节点值之和等于 sum 的路径。该题路径定义为从树的根结点开始往下一直到叶子结点所经过的结点
     * 回溯：
     * 路径：从根节点到当前节点的路径
     * 选择列表：左右子树
     * 终止条件：当到达叶子节点
     * */
    boolean backtrack82(TreeNode root,int sum){
        //base case
        if (root.left==null&&root.right==null){
            if (sum==0) return true;
            else return false;
        }
        if ((root.left!=null&&backtrack82(root.left,sum-root.left.val))||(root.right!=null&&backtrack82(root.right,sum-root.right.val))) return true;
        return false;
    }
    public boolean hasPathSum (TreeNode root, int sum) {
        if (root==null) return false;
        return backtrack82(root,sum-root.val);
    }

    /**==============================================================================================================================================
     * JZ34 二叉树中和为某一值的路径(二)
     * 输入一颗二叉树的根节点root和一个整数expectNumber，找出二叉树中结点值的和为expectNumber的<所有></所有>路径。
     * 回溯：
     * 路径：从根节点到当前节点的路径
     * 选择列表：左右子树
     * 终止条件：当到达叶子节点
     * */
    ArrayList<ArrayList<Integer>> paths=new ArrayList<>();
    void backtrack34(TreeNode root,int sum,LinkedList<Integer> path){
        if (root.left==null&&root.right==null) {
            if (sum==0) {
                paths.add(new ArrayList<>(path));
            }
        }
        //选择左子树
        if (root.left!=null){
            path.add(root.left.val);
            backtrack34(root.left,sum-root.left.val,path);
            path.removeLast();
        }
        if (root.right!=null){
            path.add(root.right.val);
            backtrack34(root.right,sum- root.right.val,path);
            path.removeLast();
        }

    }
    public ArrayList<ArrayList<Integer>> FindPath2(TreeNode root,int expectNumber) {
        if (root==null) return new ArrayList<>();
        LinkedList<Integer> path=new LinkedList<>();
        path.add(root.val);
        backtrack34(root,expectNumber-root.val,path);
        return paths;
    }


    /**==============================================================================================================================================
     * JZ84 二叉树中和为某一值的路径(三)
     * 给定一个二叉树root和一个整数值 sum ，求该树有多少路径的的节点值之和等于 sum 。该题路径定义不需要从根节点开始，也不需要在叶子节点结束，但是一定是从父亲节点往下到孩子节点
     * 对于树中每个节点，通过回溯计算从当前节点出发到叶子节点和为sum的路径数量
     * */

    public int FindPath (TreeNode root, int sum) {
        if (root==null) return 0;
        return helper84(root,sum)+FindPath(root.left,sum)+FindPath(root.right,sum);
    }
    int helper84(TreeNode node,int sum){
        if (node==null) return 0;
        sum=sum-node.val;
        int count=0;
        if (sum==0) count++;
        return count+helper84(node.left,sum)+helper84(node.right,sum);
    }

    /**==============================================================================================================================================
     * JZ36 二叉搜索树与双向链表
     * 输入一棵二叉搜索树，将该二叉搜索树转换成一个排序的双向链表。当转化完成以后，树中节点的左指针需要指向前驱，树中节点的右指针需要指向后继
     * 中序遍历，记录前驱节点
     * */
    TreeNode pre=null,root=null;
    void midOrder(TreeNode pRootOfTree){
        if (pRootOfTree==null) return ;
        midOrder(pRootOfTree.left);
        if (pre==null) {
            root=pRootOfTree;
        } else {
            pre.right=pRootOfTree;
        }
        pRootOfTree.left=pre;
        pre=pRootOfTree;
        midOrder(pRootOfTree.right);
    }
    public TreeNode Convert(TreeNode pRootOfTree) {
        if (pRootOfTree==null) return null;
        midOrder(pRootOfTree);
        root.left=null;
        pre.right=null;
        return root;
    }

    /**==============================================================================================================================================
     * JZ79 判断是不是平衡二叉树
     * 输入一棵节点数为 n 二叉树，判断该二叉树是否是平衡二叉树。它是一棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树。
     * 前序遍历，对每个节点查看其左右子树的高度，判断高度差
     * */
    int gethight(TreeNode root){
        if (root==null) return 0;
        return 1+Math.max(gethight(root.left),gethight(root.right));
    }
    public boolean IsBalanced_Solution(TreeNode root) {
        if (root==null) return true;
        int dif=Math.abs(gethight(root.left)-gethight(root.right));
        if (dif>1) return false;
        return IsBalanced_Solution(root.left)&&IsBalanced_Solution(root.right);
    }

    /**==============================================================================================================================================
     * JZ8 二叉树的下一个结点
     * 给定一个二叉树其中的一个结点，请找出中序遍历顺序的下一个结点并且返回。注意，树中的结点不仅包含左右子结点，同时包含指向父结点的next指针。
     * 1、先通过next指针找到整棵树的根节点，然后从根节点开始中序遍历存入list中，最后遍历list找到节点，返回下一个
     * 2、对于中序遍历的下一个节点可能的情况有：
     *     --1、有右子树，下一结点是右子树中的最左结点
     *     --2、无右子树，且结点是该结点父结点的左子树，则下一结点是该结点的父结点
     *     --3、无右子树，且结点是该结点父结点的右子树，则一直沿着父结点追朔，直到找到某个结点是其父结点的左子树，如果存在这样的结点，那么这个结点的父结点就是我们要找的下一结点。
     * */
    public class TreeLinkNode {
        int val;
        TreeLinkNode left = null;
        TreeLinkNode right = null;
        TreeLinkNode next = null;

        TreeLinkNode(int val) {
            this.val = val;
        }
    }
    List<TreeLinkNode> list1=new LinkedList<>();
    void midOrder(TreeLinkNode root){
        if (root==null) return;
        midOrder(root.left);
        list1.add(root);
        midOrder(root.right);
    }
    public TreeLinkNode GetNext1(TreeLinkNode pNode) {
        if (pNode==null) return null;
        TreeLinkNode root=null,temp=pNode;
        while (temp!=null){
            root=temp;
            temp=temp.next;
        }
        midOrder(root);
        int n=list1.size();
        for (int i = 0; i < n; i++) {
            if (list1.get(i)==pNode && i+1!=n){
                return list1.get(i+1);
            }
        }
        return null;
    }
    /*
     * 2、对于中序遍历的下一个节点可能的情况有：
     *     --1、有右子树，下一结点是右子树中的最左结点
     *     --2、无右子树，且结点是该结点父结点的左子树，则下一结点是该结点的父结点
     *     --3、无右子树，且结点是该结点父结点的右子树，则一直沿着父结点追朔，直到找到某个结点是其父结点的左子树，如果存在这样的结点，那么这个结点的父结点就是我们要找的下一结点。
     * */
    public TreeLinkNode GetNext(TreeLinkNode pNode) {
        if (pNode==null) return null;
        if (pNode.right!=null){
            //有右子树，下一结点是右子树中的最左结点
            pNode=pNode.right;
            while (pNode.left!=null){
                pNode=pNode.left;
            }
            return pNode;
        }
        //没有右子树
        while (pNode.next!=null){
            if (pNode.next.left==pNode){
                //且结点是该结点父结点的左子树
                return pNode.next;
            }
            //沿着父节点追溯，直到某个节点是其父节点的左子树
            pNode=pNode.next;
        }
        return null;
    }

    /**==============================================================================================================================================
     * JZ28 对称的二叉树
     * 给定一棵二叉树，判断其是否是自身的镜像（即：是否对称）
     * 递归：左右子树要镜像，root.left.left=root.right.right,root.left.right=root.right.left
     * */
    boolean isSymmetricLandR(TreeNode left,TreeNode right){
        if (left==null&&right==null)return true;
        if (left==null||right==null||left.val!=right.val) return false;
        return isSymmetricLandR(left.left,right.right)&&isSymmetricLandR(left.right,right.left);
    }
    boolean isSymmetrical(TreeNode pRoot) {
        if (pRoot==null) return true;
        return isSymmetricLandR(pRoot.left,pRoot.right);
    }

    /**==============================================================================================================================================
     * JZ78 把二叉树打印成多行
     * 给定一个节点数为 n 二叉树，要求从上到下按层打印二叉树的 val 值，同一层结点从左至右输出，每一层输出一行，将输出的结果存放到一个二维数组中返回。
     * 用队列记录每一层的节点
     * */
    ArrayList<ArrayList<Integer> > Print(TreeNode pRoot) {
        if (pRoot==null) return new ArrayList<>();
        ArrayList<ArrayList<Integer>> res=new ArrayList<>();
        Queue<TreeNode> queue=new LinkedList<>();
        queue.add(pRoot);
        while (!queue.isEmpty()){
            int levelSize=queue.size();
            ArrayList<Integer> list=new ArrayList<>();
            for (int i = 0; i < levelSize; i++) {
                TreeNode cur=queue.poll();
                list.add(cur.val);
                if (cur.left!=null) queue.add(cur.left);
                if (cur.right!=null) queue.add(cur.right);
            }
            res.add(list);
        }
        return res;
    }

    /**==============================================================================================================================================
     * JZ37 序列化二叉树
     * 请实现两个函数，分别用来序列化和反序列化二叉树，不对序列化之后的字符串进行约束，但要求能够根据序列化之后的字符串重新构造出一棵与原二叉树相同的树。
     * 先序遍历，后序遍历。层序遍历
     * */
    //序列化--先序遍历
    String Serialize(TreeNode root) {
        if (root==null) return "";
        midOrderSer(root);
        return serializeString.toString();
    }
    StringBuffer serializeString=new StringBuffer();
    void midOrderSer(TreeNode root){
        if(root==null){
            serializeString.append("#").append(",");
            return;
        }
        serializeString.append(root.val).append(",");
        midOrderSer(root.left);
        midOrderSer(root.right);
    }
    TreeNode Deserialize(String str) {
        if (str.length()==0)return null;
        String[] s = str.split(",");
        LinkedList<String> list=new LinkedList<>();
        for (String ss:s) {
            list.add(ss);
        }
        TreeNode root = helperPre(list);
        return root;
    }
    TreeNode helperPre(LinkedList<String> nodes){
        if (nodes.isEmpty())return null;
        String node = nodes.remove(0);
        if (node.equals("#")){
            return null;
        }
        TreeNode root=new TreeNode(Integer.parseInt(node));
        root.left=helperPre(nodes);
        root.right= helperPre(nodes);
        return root;
    }

    /**==============================================================================================================================================
     * JZ86 在二叉树中找到两个节点的最近公共祖先
     * 给定一棵二叉树(保证非空)以及这棵树上的两个节点对应的val值 o1 和 o2，请找到 o1 和 o2 的最近公共祖先节点。
     * 递归：从根节点判断o1，o2在根节点的哪个子树上，找到第一个o1,o2在两个子树上的节点返回
     * */

    public int lowestCommonAncestor1 (TreeNode root, int o1, int o2) {
        if (root==null) return -1;
        if (root.val==o1||root.val==o2) return root.val;
        int left = lowestCommonAncestor(root.left, o1, o2);
        int right = lowestCommonAncestor(root.right, o1, o2);
        //情况 1，如果p和q都在以root为根的树中，函数返回的即使p和q的最近公共祖先节点。
        if (left!=-1&&right!=-1)return root.val;
        //情况 2，那如果p和q都不在以root为根的树中怎么办呢？
        if (left==-1&&right==-1) return -1;
        //情况 3，那如果p和q只有一个存在于root为根的树中呢？函数就会返回那个节点。
        return left==-1?right:left;
    }

    /**==============================================================================================================================================
     * JZ68 二叉搜索树的最近公共祖先
     * 给定一个二叉搜索树, 找到该树中两个指定节点的最近公共祖先。
     * 对于该题的最近的公共祖先定义:对于有根树T的两个结点p、q，最近公共祖先LCA(T,p,q)表示一个结点x，满足x是p和q的祖先且x的深度尽可能大。在这里，一个节点也可以是它自己的祖先.
     * 1、从root判断，当root的值比pq都大时，递归去左子树找，当root的值在pq中间时，返回root，当root的值比pq都小时，递归去右子树找
     * 2、从root出发，找到从root到pq的路径。找到两条路径的分叉点即为最近公共祖先
     * */
    public int lowestCommonAncestor2 (TreeNode root, int p, int q) {
        if (root==null) return -1;
        if (root.val>p&&root.val>q) return lowestCommonAncestor2(root.left,p,q);
        if (root.val<p&&root.val<q) return lowestCommonAncestor2(root.right,p,q);
        return root.val;
    }

    public int lowestCommonAncestor (TreeNode root, int p, int q) {
        LinkedList<TreeNode> p_path=new LinkedList<>();
        LinkedList<TreeNode> q_path=new LinkedList<>();
        getPath(root,p,p_path);
        getPath(root,q,q_path);
        int res=0;
        for (int i = 0; i < p_path.size()&&i<q_path.size(); i++) {
            if (p_path.get(i).val==q_path.get(i).val){
                res=p_path.get(i).val;
            }else break;
        }
        return res;
    }
    void getPath(TreeNode root,int n,LinkedList<TreeNode> path){
        if (root==null) return;
        path.add(root);
        if (root.val==n) return;
        if (root.val>n) getPath(root.left,n,path);
        if (root.val<n) getPath(root.right,n,path);
    }
}
